// https://leetcode.cn/problems/maximum-product-of-three-numbers/
// Created by ade on 2022/8/10.
//

class Solution {
public:
    // 最粗糙的方式，需要计算两次
    int maximumProduct1(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        int len = nums.size();
        return max(nums[0] * nums[1] * nums[len - 1], nums[len - 1] * nums[len - 2] * nums[len - 3]);
    }

    // [-4,-3,-2,-1,60]
    // [-4,-3,0,1,4,60]
    // [-4,-3,0,1,60]
    // [-4,-3,0,2,4]
    // [-4,-3,1,3,4]
    // [-5,-1,1,3,4]
    // [-4,-3,0,60]
    // [-4,-3,-2,-1]
    int maximumProduct(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        int len = nums.size();
        if (nums[len - 1] <= 0 || nums[0] >= 0) {
            return nums[len - 1] * nums[len - 2] * nums[len - 3];
        }
        return max(nums[0] * nums[1] * nums[len - 1], nums[len - 1] * nums[len - 2] * nums[len - 3]);
    }
};